#define _CRT_SECURE_NO_WARNINGS
//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 1e6 + 10;
//struct node
//{
//	int l, r;
//}a[N];
//bool cmp(node& x, node& y)
//{
//	return x.l < y.l;
//}
//int main()
//{
//	int n;
//	cin >> n;
//	for (int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r;
//	sort(a + 1, a + 1 + n, cmp);
//	int rt = a[1].r;
//	int cnt = 1;
//	for (int i = 2; i <= n; i++)
//	{
//		int l=a[i].l, r = a[i].r;
//		if (rt <= l) cnt++,rt=r;
//		else
//		{
//			rt = min(r, rt);
//		}
//	}
//	cout << cnt << endl;
//	return 0;
//}
//#include<iostream>
//#include<algorithm>
//#include<cmath>
//#include<cstring>
//using namespace std;
//const int N = 1e3 + 10;
//struct node
//{
//	double l, r;
//}a[N];
//int n, d;
//bool cmp(node& x, node& y)
//{
//	return x.l < y.l;
//}
//int main()
//{
//	int c=0;
//	while (cin >> n >> d, n && d)
//	{
//		c++;
//		int flag = 0;
//		for (int i = 1; i <= n; i++)
//		{
//			double x, y; cin >> x >> y;
//			if (d  < y ) flag = 1;
//			double tmp = sqrt(d * d - y * y);
//			a[i].l = x - tmp, a[i].r = x + tmp;
//		}
//		if (flag) 
//		{
//			printf("Case %d: %d\n", c, -1);
//			continue;
//		}
//		sort(a + 1, a + 1 + n, cmp);
//		double rt = a[1].r;
//		int cnt = 1;
//		for (int i = 2; i <= n; i++)
//		{
//			double l = a[i].l, r = a[i].r;
//			if (l <= rt) rt = min(rt, r);
//			else
//			{
//				cnt++;
//				rt = r;
//			}
//		}
//		printf("Case %d: %d\n", c, cnt);
//	}
//	return 0;
//}
//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 2510;
//struct node
//{
//	int x, y;
//}a[N], b[N];
//bool cmp(node& p, node& q)
//{
//	return p.x > q.x;
//}
//int main()
//{
//	int c, m; cin >> c >> m;
//	for (int i = 1; i <= c; i++) cin >> a[i].x >> a[i].y;
//	for (int i = 1; i <= m; i++) cin >> b[i].x >> b[i].y;
//	sort(a + 1, a + 1 + c, cmp);
//	sort(b + 1, b + 1 + m, cmp);
//	int cnt = 0;
//	for (int i = 1; i <= c; i++)
//	{
//		int l = a[i].x, r = a[i].y;
//		for(int j = 1; j <= m; j++)
//		{
//			int x = b[j].x, & y = b[j].y;
//			if (x < l) continue;
//			else if (x > r) continue;
//			else if (y == 0) continue;
//			else
//			{
//				y--;
//				cnt++;
//				break;
//			}
//		}
//	}
//	cout << cnt << endl;
//	return 0;
//}
//#include<iostream>
//#include<algorithm>
//#include<queue>
//using namespace std;
//const int N = 5e4 + 10;
//struct node
//{
//	int l, r, t;
//	bool operator<(const node& a) const
//	{
//		return l > a.l;
//	}
//}a[N];
//int ret[N];
//priority_queue<node> h;
//int n;
//bool cmp(node& x, node& y)
//{
//	return x.l < y.l;
//}
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i].l >> a[i].r;
//		a[i].t = i;
//	}
//	sort(a + 1, a + 1 + n, cmp);
//	int x = a[1].l, y = a[1].r;
//	h.push({ y,1});
//	ret[a[1].t] = 1;
//	int nums = 1;
//	for (int i = 2; i <= n; i++)
//	{
//		int x = a[i].l, y = a[i].r, z = a[i].t;
//		auto q = h.top();
//		if (x <= q.l)
//		{
//			nums++;
//			ret[z] = nums;
//			h.push({ y,nums });
//		}
//		else
//		{
//			h.pop();
//			ret[z] = q.r;
//			h.push({ y,q.r });
//		}
//	}
//	cout << nums << endl;
//	for (int i = 1; i <= n; i++) cout << ret[i] << endl;
//	return 0;
//}
//#include<iostream>
//using namespace std;
//typedef long long LL;
//LL a, b, p, s=1;
//int main()
//{
//	cin >> a >> b >> p;
//	LL t = a,m=b;
//	while (m)
//	{
//		if (m & 1) s =s*t%p;
//		t = t * t%p;
//		m >>= 1;
//	}
//	s = s % p;
//	printf("%lld^%lld mod %lld=%lld\n", a, b, p, s);
//	return 0;
//}